/* 面试题 01.08. 零矩阵 */
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */

// 使用标记数组
var setZeroes = function (matrix) {
	const m = matrix.length,
		n = matrix[0].length
	const row = new Array(m).fill(false)
	const col = new Array(n).fill(false)
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (matrix[i][j] === 0) {
				row[i] = col[j] = true
			}
		}
	}
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (row[i] || col[j]) {
				matrix[i][j] = 0
			}
		}
	}
}
/**
 * 使用两个标记变量
 * 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组 以达到O(1)的额外空间
 * */
var setZeroes = function (matrix) {
	const m = matrix.length,
		n = matrix[0].length
	let flagCol0 = false,
		flagRow0 = false
	for (let i = 0; i < m; i++) {
		if (matrix[i][0] === 0) {
			flagCol0 = true
		}
	}
	for (let j = 0; j < n; j++) {
		if (matrix[0][j] === 0) {
			flagRow0 = true
		}
	}
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			if (matrix[i][j] === 0) {
				matrix[i][0] = matrix[0][j] = 0
			}
		}
	}
	for (let i = 1; i < m; i++) {
		for (let j = 1; j < n; j++) {
			if (matrix[i][0] === 0 || matrix[0][j] === 0) {
				matrix[i][j] = 0
			}
		}
	}
	if (flagCol0) {
		for (let i = 0; i < m; i++) {
			matrix[i][0] = 0
		}
	}
	if (flagRow0) {
		for (let j = 0; j < n; j++) {
			matrix[0][j] = 0
		}
	}
}
/**
 * 使用一个标记变量
 * */
var setZeroes = function (matrix) {
	const m = matrix.length,
		n = matrix[0].length

	let flagCol0 = false
	for (let i = 0; i < m; i++) {
		if (matrix[i][0] === 0) {
			flagCol0 = true
		}
		for (let j = 1; j < n; j++) {
			if (matrix[i][j] === 0) {
				matrix[i][0] = matrix[0][j] = 0
			}
		}
	}
	// 为了防止每一列的第一个元素被提前更新，我们需要
	// 重最后一行开始遍历
	for (let i = m - 1; i >= 0; i--) {
		for (let j = 1; j < n; j++) {
			if (matrix[i][0] === 0 || matrix[0][j] === 0) {
				matrix[i][j] = 0
			}
		}
		if (flagCol0) {
			matrix[i][0] = 0
		}
	}
}
setZeroes([
	[0, 1, 2, 0],
	[3, 4, 5, 2],
	[1, 3, 1, 5],
])
